#!/usr/bin/python

#
# Coursera - Cryptography course (crypto-005)
# 
# Week 6 - Assignment 4
# 
# RSA decryption
#

import gmpy2
import sys
from gmpy2 import mpz

# Ciphertext as decimal integer
ct = "220964518674103817763065611348834180174100697878928310717318391436761356" + \
		"00120538004282329650473509424343946219751512256465839967942889460764542" + \
		"04058156474898801373486412045232522932017648791666640299750918872997169" + \
		"05260832220677716000193292608700095799937240774589677736978175712672299" + \
		"51148662959627934791540"
ct = gmpy2.mpz(ct)
		
N = "17976931348623159077293051907890247336179769789423065727343008115" + \
    "77326758055056206869853794492129829595855013875371640157101398586" + \
    "47833778606925583497541085196591615128057575940752635007475935288" + \
    "71082364994994077189561705436114947486504671101510156394068052754" + \
    "0071584560878577663743040086340742855278549092581"
N = gmpy2.mpz(N)

# Encryption exponent
e = 65537

# Factorization of N obtained in challenge 1
p = "13407807929942597099574024998205846127479365820592393377723561443" + \
	 "72176403007366276889111161436232699867504054609433932083841952337" + \
	 "5986027530441562135724301"
p = gmpy2.mpz(p)
	 
q = "13407807929942597099574024998205846127479365820592393377723561443" + \
	 "72176403007377856098034893055775056966004923400219259082308516394" + \
	 "0025485114449475265364281"
q = gmpy2.mpz(q)

# e * d = 1 (mod fi(N))
fi = (p - 1) * (q-1)
d = gmpy2.invert(e, fi)
print "Decryption exponent: " , d

# msg = c^d in Zn
m = gmpy2.powmod(ct, d, N)
print "Msg: ", m.digits(16)

# After decryption, we got the message in the PKCS1.5 format.
# The plaintext if found after '00' separator
msg = "466163746f72696e67206c65747320757320627265616b205253412e"
print "".join([chr(int(msg[i*2: (i*2+2)], 16)) for i in range(0, len(msg)/2)])

